/*
 * =====================================================================================
 *    Description:  search the combination of sticks to get the minimal origianl length
 *        Version:  1.0
 *        Created:  09/12/2012 12:20:18 AM
 * =====================================================================================
 */
#include	<algorithm>
#include	<stdio.h>
#include	<string.h>
#include	<assert.h>

static int sticks[96] = {0x00};
static int totalSticks = 0;
static int sumLength = 0;
static int origCount = 0;
static int combineFillLength = 0;
static int minimal_fillspace = 0;

int sumToEnd[96];
int tempStickslen[96] = {0x00};
int combinedStickCount, origLen;

bool cmp(int a, int b)
{
    return a < b;
}

int getMinFillSpace(int n)
{
    int minfill = 5;
    for (int i = 0; i < n; ++i)
    {
        int temp = origLen - tempStickslen[i];
        if (temp > 0 && temp < minfill)
            minfill = temp;
    }
    return minfill;
}

int searchAns(int idx)
{
    int res = 0;
    if (idx >= totalSticks)
    {
        if (combinedStickCount == origCount)
            return 1;
        return 0;
    }
    //may a minimal_fillspace
    int bak_minimal_fillspace = minimal_fillspace;
    if (minimal_fillspace >= sticks[idx])
    {
        for (int k = 0; k < combinedStickCount; ++k)
        {
            if ((origLen-tempStickslen[k]) > minimal_fillspace && minimal_fillspace < sticks[idx+1])
                continue;
            int fillspace = origLen - sticks[idx] - tempStickslen[k];
            if (fillspace == 0 || (idx < totalSticks-1 && fillspace >= sticks[idx+1]))
            {
                tempStickslen[k] += sticks[idx];
                combineFillLength -= sticks[idx];
                if (fillspace > 0 && fillspace < minimal_fillspace) {
                    minimal_fillspace = fillspace;
                } else if (fillspace == 0) {
                    minimal_fillspace = getMinFillSpace(idx+1);
                }
                if (combineFillLength == 0 && combinedStickCount + (totalSticks-idx-1) == origCount)
                    return 1;
                res = searchAns(idx + 1);
                if (res == 0) {
                    tempStickslen[k] -= sticks[idx];
                    combineFillLength += sticks[idx];
                    minimal_fillspace = bak_minimal_fillspace;
                }
                else 
                    break;
            }
        }
    }
    if (res == 0)
    {
        if (combinedStickCount >= origCount)
            return 0;
        int fill_space = origLen - sticks[idx];
        if (combineFillLength + fill_space > sumToEnd[idx])
            return 0;

        tempStickslen[combinedStickCount] = sticks[idx];
        ++combinedStickCount;
        combineFillLength += fill_space;
        if (fill_space > 0 && fill_space < minimal_fillspace)
            minimal_fillspace = fill_space;
        if (combinedStickCount + (totalSticks-idx-1) == origCount)
            return 1;
        res = searchAns(idx+1);
        if (res == 0)
        {
            tempStickslen[combinedStickCount-1] = 0;
            --combinedStickCount;
            combineFillLength -= fill_space;
            minimal_fillspace = bak_minimal_fillspace;
        }
    }
    return res;
}

int main(int argc, char *argv[])
{
    int stickNo;
    int sum = 0;
    while (scanf("%d", &stickNo) == 1 && stickNo != 0)
    {
        sum = 0;
        for (int i = 0; i < stickNo; ++i)
        {
            scanf("%d", &sticks[i]);
            sum += sticks[i];
        }
        std::sort(sticks, sticks+stickNo, cmp);
        printf ( "the sorted sequence is:\n" );
        for (int i = 0; i < stickNo; ++i)
            printf ( "%d\t", sticks[i]);
        printf ( "\n" );
        sumToEnd[stickNo-1] = 0;
        for (int i = stickNo-2; i >= 0; --i)
        {
            sumToEnd[i] = sumToEnd[i+1] + sticks[i+1];
        }
        
        int candidate;
        totalSticks = stickNo;
        sumLength = sum;
        for (candidate = sticks[stickNo-1]; candidate <= sum; ++candidate)
        {
            if (sum % candidate != 0)
                continue;
            origCount = sum / candidate;
            memset(tempStickslen, 0x00, sizeof(tempStickslen));
            origLen = candidate;
            combinedStickCount = 0;
            combineFillLength = 0;
            minimal_fillspace = origLen;
            int res = searchAns(0);
            if (res == 1)
            {
                printf ( "%d\n", candidate);
                break;
            }
            else 
            {
                printf ( "%d failed\n", candidate );
            }
        }
    }
}
